Future multispectral and hyperspectral remote sensing systems and image archives will benefit from effective, high-fidelity image compression techniques. The objective of image data compression is to represent the compressed image with as few bits as possible while retaining sufficient image quality following decompression. In evaluating the effects of compression upon image data, the qualitative and quantitative effects upon the images are considered as well as end user products that are derived from the imagery through the application of environmental retrieval algorithms. Spaceborne remote sensing systems, and the image data archives for those systems will benefit from effective, high-fidelity image compression techniques. Due to practical limitations in onboard storage capacity, downlink contact time, and downlink bandwidth, it will often not be possible to capture the imagery as it was originally acquired with its full spatial, spectral, and radiometric resolution. Onboard image data compression can be used to reduce redundancy in the original input imagery, so that only the real information content need be stored or transmitted. For instance, a spaceborne panchromatic sensor with a ground footprint of one meter, a fifteen kilometer swath and twelve bits per pixel encoding, has a raw data rate of 1.26 Gbps, which exceeds envisioned downlink bandwidths and which will rapidly fill onboard storage media. Adding a multispectral capability with a lower resolution of five meters would magnify the problem by twenty percent for five additional bands. Extrapolating this example, an ambitious hyperspectral sensor can generate raw data rates at many Gbps. Remote image and sound sensing systems can benefit from the availability of high-quality compression techniques. High-resolution commercial remote sensing systems would benefit from high-quality compression methods. The use of lossless compression methods are preferred, but often are not practical in image systems requiring reliable good image quality with compression ratios of at least ten to one.
Referring to FIG. 1, a prior art image compression decompression process operates on an original input image 10 first by image compression 12 providing a compressed image 14 subjected to image decompression to provide a decompressed image 17 reconstructed from the compressed image 14. The effectiveness of the compression decompression method relates to the decompressed image quality compared to the input image 10, and the amount of data compression. The image compression and decompression are inverse operations. Image compression process 12 includes forward transformation 20, quantization 22 and entropy encoding 24. The input image 10 is compressed by image compression including forward transformation 20, quantization 22 and encoding 24 of the input image 10 to produce the compressed image 14. The input image 10 is compressed into the fewest amount of data bits of the compressed image 14 for ease of storage and transmission. The image compression 12 compresses the input image 10 into a transformed, quantized and encoded output compressed image 14 preferably having high quality image data compression at a high compression ratio. The compressed image 14 is decompressed by the image decompression process 17 including decoding 26, dequantization 28 and inverse transformation 30 to reconstruct the compressed image 14 as a decompressed image 18. Preferably, the decompressed image 18 is a lossless version of the input image 10. However, image compression 12 and decompression 16 generates artifacts in the decompressed image 18.
The input image is scanned into the forward transform, for example, using a raster row scan, a raster column scan, zig-zag, or a peano scan. The scanned pixelized data is reformatted for processing by the forward transform. The forward transform provides transformed data which is typically floating point array data, for example, formatted in an IEEE format having a sign, mantissa and exponent of thirty-two bits. The transformed data is referred to as coefficients, which are then quantized typical using scalar divisors defining a bin width, followed by truncation to produce quantized data in integer form of nearly continuous finite discrete values. Transformation and quantization disadvantageously results in a loss of image information. The quantized data may be represented, for example, as a signed two byte word, denoted as a symbol which can be encoded resulting a compressed image of codewords which may be further packed for storage and subsequently unpacked prior to decompression.
The methods of gray scaled image data compression have been typically based on two different orthogonal transform methods, the block transform method or the wavelet transform. In a block transform compression method, an original input image is segmented into blocks of pixel data, and each block of pixel data is transformed into a respective block of transformed data followed by respective block wise quantization and encoding. Block wise transformation results in blocking artifacts. In a wavelet transform, an original input image is convoluted into an entire transformed image. In block transform or wavelet transform, a plurality of finite impulse response (FIR) filters may be multiple tap digital filters and used to generate a respective plurality of filtered images having respective frequency content based upon the FIR filters. The filters operate over a predetermined block size of a plurality of pixels data points on the serially shifted input pixel data. For each shifted input pixel, and transform output coefficient is provided based upon filtering the plurality of pixel data point within the block. Various spectral filters may be used. For example, a high frequency filter and a low frequency filter can be simultaneously used to respectively simultaneously generate a high frequency image and a low frequency image. The resulting images are then down sampled, for example, by two to remove alternating data points of each filtered image to reduce the number data points back into the original input image size, such that the transformation does not compress data, but typical requires additional storage because the floating point data requires more storage than the original gray scale byte. The forward transform can be reapplied to the transform data to sufficiently capture a high fidelity two dimensional image. For example, the forwards transform could operate by row raster scan of the original input image to produce a first transformed image which is then column raster scanned and transformed to produce the final transformed image which is based upon row and column transformation for improved transformed image quality.
An exemplar block transform is the Discrete Cosine Transform. (DCT) which is used in current international standards for still image and motion picture compression. Compression blocking artifact errors results from DCT based algorithms, which include the Joint Photographic Experts Group (JPEG) compression scheme. In the international data compression standard, MPEG II Level 3 contains the specifications for audio compression which uses MLT, also called the modulated discrete cosine transform, of block lengths six and eighteen. The DCT compression may include a split-radix approach, which is the fastest known DCT algorithm. For compression with a bit rate below 1 bit per pixel, the DCT disadvantageously results in objectionable blocking artifacts. In applying DCT method to obtain high compression ratios at bit. rates below one bit per pixel, the block boundaries defects often appear in the reconstructed decompressed images. Such defects are blocking artifacts. In the JPEG standard, a two-dimensional DCT is used for still image compression and decompression. However, at high compression ratios, the DCT based JPEG method has produced serious blocking artifacts in the decompressed images.
In the DCT compression method, the image is segmented into small blocks, such as an 8.times.8 pixel by pixel square, prior to compression. The net output sizes of the DCT are eight pixel by eight pixel blocks. The transformed coefficients from the DCT are floating point numbers. The quantization process converts the floating point transformed coefficients into positive or negative integers by first dividing each of the floating-point transformed coefficient by a corresponding integer in a quantization matrix, and then rounding off the results into integers. In the DCT transform domain, the coefficient at the upper-left corner of the 8.times.8 matrix is the lowest frequency term. The lower-right corner is the highest frequency term usually a small number. Taking advantage of human visual characteristics, many of the high frequency terms may be truncated by the quantization process with only a small loss of visual image quality. However, in the DCT method, the quantization causes the blocking effect.
The wavelet transform is a convolution transform of the entire image. The entire original input image is serially shifted into the wavelet transform to produce an entire transform image. The wavelet transform must convolve the image wise the entire image which requires large temporary memory stores and require serial slow processing. Even though the wavelet transform method does not produce serious blocking artifacts at a low bit rate, the wavelet transform processing speed in conventional implementations is disadvantageously slow because of the image wise convolution. The Modulated Lapped Transform (MLT) is a hybrid transform. The desirable property of the MLT is the advantageous high speed of the DCT and the reduced blocking artifacts of wavelet transform. The MLT employs a scan, which may be for example, a raster scan or a peano scan for inputing data into the MLT. The MLT uses a subband filter bank and the window used in MLT spans two DCT blocks, but the window shifts block-by-block. Thus, the MLT performs not only a fast DCT but also a blockwise convolution for reduce blocking artifacts. The use of overlapped windows in MLT obviates many of the blocking artifacts occurring at low-bit rates for the DCT compression method.
In both of the DCT and MLT compression methods, the image is segmented into small blocks, for example, 8 pixel by 8 pixel square, prior to compression. However, in the MLT, there are initially 16 pixels, in one dimension, being shifted into the MLT. These 16 pixels represent the overlapping of two 8 pixel blocks. Subsequently, the MLT retains the latter 8 pixels and inputs 8 more for transformation. The net output sizes in both DCT and MLT are still 8 pixel by 8 pixel blocks. The transformed coefficients from the DCT and MLT are both floating-point numbers. In both the DCT and MLT transform domains, the coefficient at the upper-left corner of the 8.times.8 matrix is the lowest frequency term. The lower-right corner is the highest frequency term usually a small number. In DCT method the quantization causes the blocking effect whereas in MLT method, the high frequency terms roll off much faster than the DCT method because of the use of overlapping windows. Thus, there are mare high frequency terms that have been saved from quantization. Consequently, the reconstructed image quality is superior when MLT is compared to DCT for the same bit rate.
The subsequent entropy encoding assigns a binary code to the quantized transformed coefficients. Such a lossless process is called entropy encoding because the length of the code is proportional to the entropy. The most probable lowest entropy sample is coded with the shortest code. A commonly used entropy encoder is the Huffman code, even though JPEG standard also allows for the Arithmetic code. However, these entropy encoders prefer one-dimensional input data streams. To convert the two-dimensional quantized block into a one-dimensional data stream for entropy encoding, a zig-zag scan pattern according to JPEG specification for DCT may be used for both DCT and MLT. The zig-zag scan increases the zero run length, thus increasing the compression ratio when the run is coded in the entropy encoders. The input to the entropy encoders are fixed-length binary numbers representing the quantized samples and run lengths. However the output from the entropy encoders are variable-length binary codes and a data buffer is needed at the encoder output. The data buffer regulates the output data rate for the fixed bandwidth channels, and generate data packets for error protection during transmission.
An MLT transform is typically defined by a transform kernel. The MLT transform kernel is the product of a window function W and a modulation function F both operating over a plurality of blocks of M pixels over a window of N pixels. The transform kernel W(n)F(k,n) is multiplied by input data stream X(n) for n pixels of the window for k pixels of each output block to provide a transformed output Z(k) summed for each element of the pixel input stream, that is, Z(k)=c.SIGMA.X(n) W(n) F(k,n), for n=1.fwdarw.N for each k=1.fwdarw.M, with a scalar c. The window function may be for example a half sin function, W(n)=sin (2n-1) (.pi./2N)!. The modulation function may be a discrete cosine function with a shifted phase, F(k,n)=cos(.pi./4M) (2k-1) (2n+M-1)!, where N is the window size, e.g. 16, M is the block size, e.g. 8, and n is the running index of the input stream, 1.fwdarw.N for the window size, and k an output pixel index, 1.fwdarw.M for the block size. A scalar c, and a normalization factor of square root of (2/M) are incorporated into the transform function. The input pixel is represented by X(n). The transform function can be expressed as a summation of a product of the window sin function and the modulation cosine function and the input pixel X(n) for n=1.fwdarw.N the window size and for each k=1.fwdarw.M, the block size. EQU Z(k)=c.sqroot.2/M.SIGMA..sub.n=1.sup.N {sin (2n-1)(.pi./2N)! EQU cos (.pi./4M)(2k-1)(2n+M-1)!X(n)}
The availability of a cost-effective VLSI hardware implementation can be applied to compression algorithms. Considerations implementation feasibility limit the usefulness of MLT method. The complexity of the VLSI architecture implementation is determined by the form transform function equation. The mathematical manipulation of the MLT transform equation into alternative form of expressions can be translated into alternative hardware architecture configuration.
One such mathematical manipulation of the transform function equation is to convert the kernel transform function of the sine cosine product into a sum of sine function using the trigonometric relation 2 sin (x) cos (y)=sin (x+y)+sin (x-y). The resulting MLT architecture is a fast MLT system comprising a front end infinite impulse response (IIR) filter operating the input data stream X(n) but disadvantageously consists of eight modules, with each module using six multipliers. Another such mathematical manipulation of the transform function equation is to decompose the MLT into a parallel butterfly bank of multipliers with many DCT modules. A fast DCT processor can be designed according to a Split-Radix DCT method disclosed in U.S. Pat. No. 5,408,425 by Hou on Apr. 18, 1995.
Even though the fast MLT and the fast DCT methods can process images at very high speed on a general-purpose computer or on a programmable digital signal processor, such a fast DCT processor is not tailored for VLSI chip implementations because of the complexity of the resulting equations. These two MLT implementations resulting from the respective mathematical manipulation of the MLT transform function require too many interconnects and too many arithmetic processing units. Important prerequisites of VLSI designs are the use the least number of multipliers and interconnections in order to decrease chip layout complexity and silicon area. Decreasing the number of interconnects and the number of multipliers would save valuable silicon areas in a VLSI chip and simplifies the layouts and routing, for cost effective practical production. Repetitive cost effective VLSI designs and layouts are enhanced by modular designs. These MLT designs are not modular because the interconnections are not local to the individual multipliers disadvantageously complicating the VLSI implementation.
An MLT image compression decompression algorithm can be implemented using various VLSI architectures realized from respective alternatives form of the manipulated transform equation. It is desirable in VLSI designs to use the least number of multipliers and interconnections in order to decrease the chip layout complexity and silicon area. Prior MLT algorithms require the use of many multipliers and interconnections between the multipliers. Consequently, the design of MLT unit will disadvantageously not be modular because the interconnections are not local to the individual multipliers. These conventional MLT algorithms use the FIR digital filters or the in-place Fast Fourier Transform (FFT) which of all disadvantageously require many multipliers and interconnects. The FFT filter disadvantageously requires that the input data length be an integer power of two. These and other disadvantages are solved or reduced using the invention.